# leetcode 20 有效的括号匹配

# 不匹配的场景有三个：
# 1. 左括号多了
# 2. 右括号多了
# 3. 左右括号不匹配
# 思路：
# 从左向右遍历，遇到左括号，则将右括号加入到栈中；
# 遇到右括号，则与栈顶元素进行比较，如果相同，则消除栈顶元素
# 当完全匹配的时候，字符串遍历完，栈应当为空
# 第一种不匹配情况，遍历完了，栈不为空
# 第二种不匹配情况，字符串还没遍历完，栈已经为空
# 第三种不匹配情况，在遍历过程中，遇到了右括号与栈顶元素不相同

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        left = {'(': 0,  '{': 1,  '[': 2}
        right = {0: ')', 1:  '}', 2:  ']'}
        n = len(s)
        for i in range(n):
            x = s[i]
            if x in left:
                stack.append(right[left[x]])
            else:
                if len(stack) == 0:
                    return False
                top = stack[-1]
                if top == x:
                    stack.pop()
                else:
                    return False
        if len(stack) != 0:
            return False
        else:
            return True
